package com.ln.prac.base.xiaoao.dataStructure;

import java.util.HashSet;
import java.util.Set;
import java.util.function.Predicate;

/**
 * MyLinkedList
 *
 * @Author zhangj
 * @Date 2023/2/2 22:57
 */
public class MyLinkedList<T> {

    public static class Node<T> {
        Node<T> next = null;
        Node<T> prev = null;
        T data;

        public Node(T data) {
            this.data = data;
        }

        public T getData() {
            return data;
        }

        public Node<T> getNext() {
            return next;
        }

        public Node<T> getPrev() {
            return prev;
        }
    }

    public Node<T> head = null;

    Node<T> tail = null;

    /**
     * 头部插入
     *
     * @param data
     */
    public void insert(T data) {
        Node<T> node = new Node<>(data);
        node.next = head;
        head = node;
    }

    /**
     * O(n)
     *
     * @param predicate
     * @return
     */
    public Node<T> find(Predicate<T> predicate) {
        Node<T> point = head;
        while (point != null) {
            if (predicate.test(point.data)) {
                return point;
            }
            point = point.next;
        }
        return null;
    }

    /**
     * O(n)
     *
     * @param node
     */
    public void remove(Node<T> node) {
        if (head == null) {
            return;
        }
        if (head == node) {
            head = head.next;
            return;
        }

        Node<T> slow = head;
        Node<T> fast = head.next;
        while (fast != node && fast != null) {
            slow = fast;
            fast = fast.next;
        }
        if (fast != null) {
            // 考虑内存回收的问题
            slow.next = fast.next;
        }
    }

    public Integer size() {
        Node<T> point = head;
        int size = 0;
        while (point != null) {
            point = point.next;
            ++size;
        }
        return size;
    }

    /**
     * 链表反转
     */
    public void reverse() {
        // prev | current | next
        Node<T> prev = null;
        Node<T> current = head;
        Node<T> next;
        while (current != null) {
            // 将当前节点的下一个节点存放起来
            next = current.next;
            // 反转当前节点
            current.next = prev;
            // 将当前阶段存放起来
            prev = current;
            current = next;
        }
        head = prev;
    }

    /**
     * 使用递归进行链表反转
     * 过程：
     * A->B->C->D
     * <pre>
     * // 压栈过程
     * A
     * B
     * C
     * D
     * // 出栈过程
     * D
     * C，C->D ==> D->C
     * B, B->C ==> C->B ==> D->C->B
     * A, A->B ==> B->A ==> D->C->B->A
     * </pre>
     */
    public Node<T> reverseRecursion(Node<T> head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node<T> rest = reverseRecursion(head.next);
        head.next.next = head;
        head.next = null;
        return rest;
    }

    /**
     * 判断是否成环，使用Hash表的思路
     */
    public boolean hasLoopWithHash() {
        Set<Node<T>> set = new HashSet<>();
        Node<T> p = head;
        while (p != null) {
            if (set.contains(p)) {
                return true;
            }
            set.add(p);
            p = p.next;
        }
        return false;
    }

    /**
     * 使用快慢指针判断是否成环
     */
    public boolean hasLoopWithFastSlow() {
        if (head == null || head.next == null) {
            return false;
        }
        Node<T> slow = head;
        Node<T> fast = head.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }


}
